package main.图;

/**
 * @author tmh
 * @date 2024/7/25 10:40
 * @description //这个人写的这个文章写的真好，醍醐灌顶了
 * //https://leetcode.cn/problems/number-of-islands/solutions/211211/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/?envType=study-plan-v2&envId=top-interview-150
 */
public class T200岛屿数量 {
    /**
     * 图的问题基本上都是一个套路，用那个框架就行
     *
     * @param grid
     * @return
     */
    public int numIslands(char[][] grid) {
        //定义一个岛屿数量
        int count = 0;
        int row = grid.length;
        int col = grid[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j]=='1'){
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    private void dfs(char[][] grid, int i, int j) {
        if (!isArea(grid, i, j)) {
            return;
        }
        //如果这个格子不是陆地，直接返回
        if (grid[i][j] != '1') {
            return;
        }
        //把当前格子标记为访问过
        grid[i][j] = '2';
        //往上下左右四个方向进行遍历
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);

    }

    /**
     * 判断i，j在不在矩阵里面
     *
     * @param grid
     * @param i
     * @param j
     * @return
     */
    private boolean isArea(char[][] grid, int i, int j) {
        return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length;
    }
}
